package com.kevinkk.dp;

/**
 * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

public class BestTimeToBuyAndSellStockIV {
    class Solution {
        public int maxProfit(int k, int[] prices) {
            int length = prices.length;
            int[][] dp = new int[length][k * 2];
            for (int j = 0; j < 2 * k; j++) {
                if (j % 2 == 0) dp[0][j] = -prices[0];  // 第 j 次持有
                if (j % 2 == 1) dp[0][j] = 0;           // 第 j 次不持有
            }

            for (int i = 1; i < length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
                for (int j = 1; j < 2 * k; j++) {
                    if (j % 2 == 1) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                    if (j % 2 == 0) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }
            }

            int res = 0;
            for (int j = 0; j < 2 * k; j++) {
                res = Math.max(res, dp[length - 1][j]);
            }
            return res;

        }
    }
}
